package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        Integer[] arr = new Integer[] { 2, 4, 6, 8, 2, 3, 5, 6, 7, 9, 3, 6, 4, 7, 4, 9, 1 };
        // after sort: 1, 2, 2, 3, 3, 4, 4, 4, 5, 6,6, 6, 7, 7, 8, 9, 9
        System.out.println(isRepeat(arr));
        System.out.println(repeatCount(arr));
        System.out.println(frequencyMax(arr));
    }

    /**
     * 判断数组中是否存在重复元素
     * 
     * @param arr
     * @return
     */
    public static <T extends Comparable<T>> boolean isRepeat(T[] arr) {

        T[] arrCopy = (T[]) new Comparable[arr.length];
        System.arraycopy(arr, 0, arrCopy, 0, arr.length);
        sort(arr);
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i].compareTo(arr[i + 1]) == 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取数组中有多少个重复元素
     * 
     * @param arr
     * @return
     */
    public static <T extends Comparable<T>> int repeatCount(T[] arr) {

        T[] arrCopy = (T[]) new Comparable[arr.length];
        System.arraycopy(arr, 0, arrCopy, 0, arr.length);
        sort(arr);
        int repeatCount = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i].compareTo(arr[i + 1]) == 0) {
                repeatCount++;
                i++;
                while (i < arr.length - 1 && arr[i].compareTo(arr[i + 1]) == 0) {
                    i++;
                }
            }
        }
        return repeatCount;
    }

    /**
     * 获取数组中出现频率最大的元素，如果有多个，则返回第一个
     * 
     * @param arr
     * @return
     */
    public static <T extends Comparable<T>> T frequencyMax(T[] arr) {

        T[] arrCopy = (T[]) new Comparable[arr.length];
        System.arraycopy(arr, 0, arrCopy, 0, arr.length);
        sort(arr);
        int frequency = 0;
        T max = null;
        for (int i = 0; i < arr.length - 1; i++) {
            int tempFreq = 1;
            while (i < arr.length - 1 && arr[i].compareTo(arr[i + 1]) == 0) {
                i++;
                tempFreq++;

            }
            if (frequency < tempFreq) {
                frequency = tempFreq;
                max = arr[i];
            }
        }
        return max;
    }

    /**
     * 稳定的归并排序
     * 
     * @param arr
     * @param id
     */
    private static <T extends Comparable<T>> void sort(T[] arr) {

        T[] aux = (T[]) new Comparable[arr.length];
        sort(arr, aux, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] arr, T[] aux, int low, int high) {

        if (high <= low) {
            return;
        }
        int mid = low + ((high - low) >> 1);
        sort(arr, aux, low, mid);
        sort(arr, aux, mid + 1, high);
        merge(arr, aux, low, mid, high);
    }

    private static <T extends Comparable<T>> void merge(T[] arr, T[] aux, int low, int mid, int high) {

        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }

        int k = low;
        while (i <= mid && j <= high) {
            if (aux[i].compareTo(aux[j]) <= 0) {
                arr[k++] = aux[i++];
            } else if (aux[i].compareTo(aux[j]) > 0) {
                arr[k++] = aux[j++];
            }
        }
        while (i <= mid) {
            arr[k++] = aux[i++];
        }
        while (j <= high) {
            arr[k++] = aux[j++];
        }
    }
}